/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Kevin Lim
 */

#include "base/intmath.hh"
#include "cpu/edge/pred/tournament_perceptron.hh"
#include "cpu/base.hh"

template<class Impl>
TournamentPerceptron<Impl>::TournamentPerceptron(DerivEdgeCPUParams *params)
    :choiceHistoryBits(params->choiceHistoryBits),
     choicePredictorSize(params->choicePredictorSize),
     choiceCtrBits(params->choiceCtrBits),
     blockShiftAmt(params->blockShiftAmt)
{

    perceptron_global = new PerceptronBP<Impl>(params,0);

    perceptron_local = new PerceptronBP<Impl>(params,1);
    
    choiceHistoryFile.resize(Impl::MaxInFlightBlockNum);
    
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i )
        choiceHistoryFile[i] = 0;
    
    if (!isPowerOf2(choicePredictorSize)) {
        fatal("Invalid choice predictor size!\n");
    }
    //Clear the choice history
    for (int i = 0; i < Impl::MaxThreads; ++i)
        choiceHistory[i] = 0;
    // Setup the choice history mask
    choiceHistoryMask = (1 << choiceHistoryBits) - 1;
    
    //Setup the array of counters for the choice predictor
    choiceCtrs.resize(choicePredictorSize);

    for (int i = 0; i < choicePredictorSize; ++i)
        choiceCtrs[i].setBits(choiceCtrBits);

    // @todo: Allow for different thresholds between the predictors.
    threshold = (1 << (choiceCtrBits - 1)) - 1;
    threshold = threshold / 2;

    localChoosen = 0;

    globalChoosen = 0;
}

template<class Impl>
TournamentPerceptron<Impl>::~TournamentPerceptron()
{
    DPRINTF(EdgePredUnit,"Tournament destructed!\n");
}

template<class Impl>
void
TournamentPerceptron<Impl>::reset()
{	
    perceptron_local->reset();

    perceptron_global->reset();
    
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i )
	choiceHistoryFile[i] = 0;
	
    //Clear the choice history
    for (int i = 0; i < Impl::MaxThreads; ++i)
        choiceHistory[i] = 0;
    
    for (int i = 0; i < choicePredictorSize; ++i)
        choiceCtrs[i].setBits(choiceCtrBits);

    localChoosen = 0;

    globalChoosen = 0;
}

template<class Impl>
inline
uint32_t
TournamentPerceptron<Impl>::calcChoiPredIdx(Addr &block_addr,uint32_t history)
{
    uint32_t index = (history ^ (block_addr >> blockShiftAmt)) & choiceHistoryMask;
    return index;
}

template<class Impl>
TheISA::ExitID
TournamentPerceptron<Impl>::lookup(BlockID blockID, BlockID oldest_blockID, 
        Addr &block_addr, int addr_space_ID, ThreadID tid)
{
    ExitID local_prediction;
    ExitID global_prediction;
	
    uint32_t choice_history;
    uint32_t choice_predictor_idx;
    bool choice_prediction;
    ExitID prediction;

    uint32_t choice_history_new;

    local_prediction = perceptron_local->lookupExit(block_addr,tid);
    
    global_prediction = perceptron_global->lookupExit(block_addr,tid);
    
    //Get choice history
    choice_history = choiceHistory[tid] & choiceHistoryMask;
    choice_predictor_idx = calcChoiPredIdx(block_addr,choice_history);
    //Lookup in the choice predictor to see which one to use
    choice_prediction = choiceCtrs[choice_predictor_idx].read() > threshold;
    if(choice_prediction) {
        globalChoosen ++;
    } else {
        localChoosen ++;
    }
    // Final prediction
    prediction= choice_prediction ? global_prediction : local_prediction;
    DPRINTF(EdgePredUnit,"BP: global prediction = %i, local_prediction = %i for %#x.\n",
		global_prediction,local_prediction,block_addr);
     // Speculative update
    unsigned index = blockID&(Impl::MaxInFlightBlockNum -1); 

    perceptron_global->speculativeUpdate(tid,blockID,prediction);

    choiceHistoryFile[index] = choice_history;
    choice_history_new = ((choice_history << 3) | (prediction & 7) ) & choiceHistoryMask ;
    choiceHistory[tid] = choice_history_new;
    DPRINTF(EdgePredUnit, "localChoosen = %i, globalChoosen = %i.\n",localChoosen,
    		globalChoosen);
    return prediction;
 }

template<class Impl>
void
TournamentPerceptron<Impl>::update(BlockID blockID, Addr &block_addr, 
        int addr_space_id,ExitID actual_exitID,ThreadID tid)
{
    uint32_t choice_predictor_hist;
    uint32_t choice_predictor_idx;
    uint32_t index = blockID &(Impl::MaxInFlightBlockNum -1);
    TheISA::ExitID global_prediction;
    TheISA::ExitID local_prediction;
    
    assert(actual_exitID >= 0 && actual_exitID <= 7);
    choice_predictor_hist = choiceHistoryFile[index];

    local_prediction = perceptron_local->update(blockID,block_addr,actual_exitID);

    global_prediction = perceptron_global->update(blockID,block_addr,actual_exitID);
    choice_predictor_idx = calcChoiPredIdx(block_addr, choice_predictor_hist);
    if (local_prediction!= global_prediction) {
        if (local_prediction == actual_exitID) {
            choiceCtrs[choice_predictor_idx].decrement();
	 } else if(global_prediction == actual_exitID) {
            choiceCtrs[choice_predictor_idx].increment();
	 }
    }
}

template<class Impl>
void
TournamentPerceptron<Impl>::squash(BlockID blockID,ExitID exitID,ThreadID tid)
{
    unsigned choice_history;
    unsigned index = blockID&(Impl::MaxInFlightBlockNum -1) ;

    perceptron_global->squash(blockID,exitID,tid);
 
    choice_history = choiceHistoryFile[index];
    choiceHistory[tid] = ((choice_history << 3) | (exitID & 7) ) & choiceHistoryMask ;
    DPRINTF(EdgePredUnit,"Squashing BP to Block [bid:%i].\n",blockID);
}

template<class Impl>
void
TournamentPerceptron<Impl>::squash(BlockID blockID,ThreadID tid)
{
    unsigned index = blockID&(Impl::MaxInFlightBlockNum -1);
    unsigned choice_history;

    perceptron_global->squash(blockID,tid);

    choice_history = choiceHistoryFile[index];
    choiceHistory[tid] = choice_history;
}

